import java.util.ArrayList;

public class PackLine {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ArrayList<Integer> l = new ArrayList<Integer>();
		l.add(8);
		l.add(7);
		l.add(8);

		PackLine p = new PackLine(l);
		p.doPack();
		p.printRes();

		ArrayList<Integer> l1 = new ArrayList<Integer>();
		l1.add(8);
		l1.add(4);
		l1.add(11);
		l1.add(25);
		l1.add(9);
		l1.add(21);
		PackLine p1 = new PackLine(l1);
		p1.doPack();
		p1.printRes();

	}

	/*
	 * [input i][rotate l/r][result for left/right/current position], negative
	 * value indicate current position is in left, else in right
	 */
	private ArrayList<Integer> input = new ArrayList<Integer>();
	private Integer[][][] resList = new Integer[10][1024][3];

	PackLine(ArrayList<Integer> l) {
		input = l;
	}

	void doPack() {
		/* First rotation */

		resList[0][0][0] = input.get(0);
		resList[0][0][1] = 0;
		resList[0][0][2] = input.get(0);

		resList[0][1][0] = 0;
		resList[0][1][1] = 0 - input.get(0);
		resList[0][1][2] = 0 - input.get(0);

		for (int i = 1; i < input.size(); i++) {
			for (int j = 0; j < Math.pow(2, i); j++) {

				// System.out.println(i);
				int currentRightVal = resList[i - 1][j][0];
				int currentLeftVal = resList[i - 1][j][1];
				int currentPosition = resList[i - 1][j][2];

				/* Current position is in left */
				/* Rotate right */
				if (currentPosition < 0) {
					if (Math.abs(currentPosition) > input.get(i)) {
						// Result stays
						resList[i][j * 2][0] = currentRightVal;
						resList[i][j * 2][1] = currentLeftVal;
						resList[i][j * 2][2] = currentPosition + input.get(i);

					} else if (Math.abs(currentPosition) <= input.get(i)) {
						resList[i][j * 2][1] = currentLeftVal;

						int dif = currentPosition + input.get(i);
						resList[i][j * 2][2] = dif;

						if (dif > currentRightVal)
							resList[i][j * 2][0] = dif;
						else
							resList[i][j * 2][0] = currentRightVal;

					}

					/* Rotate left */

					int dif = Math.abs(currentLeftVal - currentPosition);
					if (dif > input.get(i))
						resList[i][j * 2 + 1][1] = currentLeftVal;
					else
						resList[i][j * 2 + 1][1] = currentLeftVal
								- input.get(i) + dif;
					resList[i][j * 2 + 1][0] = currentRightVal;
					resList[i][j * 2 + 1][2] = currentPosition - input.get(i);
				}

				/* Current position is in right */

				else {

					/* Rotate left */
					if (currentPosition >= input.get(i)) {

						// Result stays
						resList[i][j * 2 + 1][0] = currentRightVal;
						resList[i][j * 2 + 1][1] = currentLeftVal;
						resList[i][j * 2 + 1][2] = currentPosition
								- input.get(i);

					} else if (currentPosition < input.get(i)) {
						resList[i][j * 2 + 1][0] = currentRightVal;

						int dif = Math.abs(input.get(i) - currentPosition);
						resList[i][j * 2 + 1][2] = dif;
						if (dif > Math.abs(currentLeftVal))
							resList[i][j * 2 + 1][1] = 0 - dif;
						else
							resList[i][j * 2 + 1][1] = currentLeftVal;
					}

					/* Rotate right */

					int dif = currentRightVal - currentPosition;
					if (dif > input.get(i))
						resList[i][j * 2][0] = currentRightVal;
					else
						resList[i][j * 2][0] = currentRightVal + input.get(i)
								- dif;
					resList[i][j * 2][1] = currentLeftVal;
					resList[i][j * 2][2] = currentPosition + input.get(i);
				}

			}
		}

	}

	void printRes() {
		int resVal = 0;
		int temp = 0;
		resVal = resList[input.size() - 1][0][0]
				+ Math.abs(resList[input.size() - 1][0][1]);
		for (int i = 1; i < Math.pow(2, input.size()); i++) {

			temp = resList[input.size() - 1][i][0]
					+ Math.abs(resList[input.size() - 1][i][1]);
			if (temp < resVal)
				resVal = temp;
		}

		System.out.println("The solution for" + this.input.toString() + " is "
				+ resVal + "!");

	}
}
